Stereo matching is a method in computer vision to determine a depth of a scene, or a distance from a camera to the scene. The method uses multiple input images of the scene taken from different positions. The depth of a location in the scene corresponds to an apparent disparity between the locations in the images. Disparity matching can consider illumination, reflections, texture, and the like, to avoid mismatch errors. Occluded locations are problematic. Stereo matching assume that a stereo pair of input images is epipolar rectified, which ensures that lines-of-sight are parallel, and the matching only has to be in one dimension, horizontally when the cameras or views are displaced horizontally, and the disparity is inversely proportional to the depth. That is, small disparities correspond to large depths, and large disparities correspond to small depths.
Disparity estimation can produce a disparity map. The disparity map is a scaled version of a depth map. That, the disparity values can be converted to depth values.
Image rectification is a usual preprocessing step for disparity estimation. Generally, rectification determines matching locations in the pair of input images, and a transform to align the locations, such that it appears that the images appear as if the cameras were aligned. Rectification is complex and error prone. Even with accurate methods, it is possible that some stereo pairs produce degenerate configurations for which there is no transform. Rectification also warps the input images, and features become distorted. The matching can still fail in regions where a vertical disparity is significantly large.
One alternative uses an optical flow, which does perform a two-dimensional search. However, the optical flow is not identical to the disparity, and consequently, post-rectification is needed to convert the flow to disparity.
Thevenon et al., in “Dense Pixel Matching Between Unrectified and Distorted Images Using Dynamic Programming” International Conference on Computer Vision Theory and Application—2009, describe a method for pixel matching based on dynamic programming. The method does not require rectified images. The matching extends dynamic programming to a larger dimensional space by using a 3D scoring matrix so that correspondences between a scanline and a whole image can be determined.
Nalpantidis et al., in “Dense Disparity Estimation Using a Hierarchical Matching Technique from Uncalibrated Stereo” International Workshop on Imaging Systems and Techniques—2009, describes sub-pixel matching, using sub-sample positions and integer-sample positions between non-rectified stereo image pairs image pairs, and selecting the position that gives the best match. Therefore, that disparity estimation algorithm performs a 2-D correspondence search using a hierarchical search pattern. The disparity value is defined using the distance of the matching position. Therefore, the proposed algorithm can process, maintaining the computational load within reasonable levels.
U.S. Publication 20070064800 discloses method for estimating disparity to encode a multi-view moving picture for encoded macroblocks.